package lower_ceil04;

/**
 * 实现lower_ceil：大于等于target的最小索引值
 * 如果数组中存在元素，返回最小索引
 * 如果数组中不存在元素，返回upper
 */
public class BinarySearch {

    public static <E extends Comparable<E>> int lowerCeil1(E[] data, E target) {
        int l = 0, r = data.length;
        while (l < r) {
            int mid = l + (r - l) / 2;
            // 在 upper 中，这里是 data[mid].compareTo(target) <= 0
            // 但是，对于 lower_ceil 来说，在 data[mid] == target 的时候，有可能是解
            // 所以在等于的情况下，不能排除掉 data[mid] 的值。在等于的情况下，应该归入下面的 else 中做处理
            // 也就是，data[mid] == target 的时候可能是解，也可能有更小的解在左边，应该去更新右边界
            if (data[mid].compareTo(target) >= 0) r = mid;
            else l = mid + 1;
        }
        return r;
    }

    public static <E extends Comparable<E>> int lowerCeil(E[] data, E target) {
        int l = 0, r = data.length - 1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            // 在 upper 中，这里是 data[mid].compareTo(target) <= 0
            // 但是，对于 lower_ceil 来说，在 data[mid] == target 的时候，有可能是解
            // 所以在等于的情况下，不能排除掉 data[mid] 的值。在等于的情况下，应该归入下面的 else 中做处理
            // 也就是，data[mid] == target 的时候可能是解，也可能有更小的解在左边，应该去更新右边界
            if (data[mid].compareTo(target) >= 0) r = mid + 1;
            else l = mid + 1;
        }
        return r;
    }

    public static void main(String[] args) {

        Integer[] arr = {1, 1, 3, 3, 5, 5};
        for (int i = 0; i <= 6; i++)
            System.out.print(BinarySearch.lowerCeil(arr, i) + " ");
        System.out.println();
    }


}
